Subarray Sum Equals K
Leetcode #560 | Medium | Префикс | Хэш-таблицы
Идея
Префиксная сумма pref[i] это сумма от 0 до i-го (включительно) элемента
Чтобы посчитать sum(i,...,j) = pref[j] - pref[i-1]
sum = k; pref[i-1] = pref[j] - k;
К ответу прибавляем количество pref[j]-k из мапы, записываем pref[i-1] в мапу
Изнчально в мапе {0: 1} - префикс 0 встретился ровно 1 раз, очевидно
Big-O
- Время
O(N) - Память
O(N)
Код
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int pref = 0;
Map<Integer, Integer> temp = new HashMap<>();
temp.put(0, 1);
for (int num : nums) {
pref += num;
if (temp.containsKey(pref - k)) {
count += temp.get(pref - k);
}
temp.put(pref, temp.getOrDefault(pref, 0) + 1);
}
return count;
}
}